Error correction codes are often employed in communication systems to provide increased resilience to channel noise. Generally, error correction encoding techniques typically employ convolutional, block or concatenated coding of the data before the signal is modulated so that errors introduced by noise and interference on the channel may be corrected. One popular family of linear low rate error correction codes having large minimum distances is first order Reed-Muller codes. Each family of error correction codes has a dual code. The dual code for binary Reed-Muller codes are the binary Hamming codes.
The received signal, which is typically corrupted by the noise and interference on the channel, must be decoded at the receiver. Typically, maximum a posteriori decoding techniques are applied to decode signals encoded using error correction codes to make maximum probability decisions about each transmitted bit. For a detailed discussion of Hamming codes and the decoding thereof, see, for example, T. Kasami et al., “On the Optimum Bit Orders With Respect to the State Complexity of Trellis Diagrams for Binary Linear Codes,” IEEE Trans. Inf. Theory, vol. IT-39, 242–45 (January, 1993) or T. Kasami et al, “On Complexity of Trellis Structure of Linear Block Codes,” IEEE Trans. Inf. Theory, vol. IT-39, 1057–64 (January, 1993), incorporated by reference herein.
One particular implementation of the MAP decoding algorithm, commonly referred to as the BCJR algorithm, was proposed in L. R. Bahl, J. Cocke, F. Jelinek and J. Raviv, “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate”, IEEE Trans. Inform. Theory, V. IT-20, 284–287 (March, 1974), incorporated by reference herein. The BCJR algorithm is a symbol-by-symbol decoder based on a trellis representation of a code. The BCJR algorithm for binary Hamming codes has a complexity that is proportional to n2, where n is the code length. A need exists for a method and apparatus for decoding Hamming and extended Hamming codes having reduced complexity.